package leetcode_动态规划._09字符串编辑;

/**
 * @author yzh
 * @data 2021/3/23 15:46
 * 只有两个键的键盘
 * 记事本上有一个 'A'，只有两个操作 --- 复制全部 和 粘贴
 * | 0    | 1    | 2    | 3    | 4    | 5    | 6    | 7    | 8    | 9    | 10   | 11   | 12   | 13   | 14   |
 * | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- |
 * | 0    | 0    | 2    | 3    | 4    | 5    | 5    | 7    | 6    | 6    | 7    | 11   | 7    | 13   | 9    |
 * dp[i] 表示 i 个 'A' 的最少操作次数
 * 当 i 为质数(素数)时，dp[i] = i
 * 为合数时，比如 10，取它合数中的一对值 --- 2 和 5，则 dp[10] = dp[2] + dp[5]
 * 要求出 n 的合数或者素数
 */
public class _650 {
    public static void main(String[] args) {
        System.out.println(new _650().minSteps(3));
    }

    public int minSteps(int n) {
        if (n == 1) return 0;
        int judge = judge(n);
        if (judge == 1) return n;
        int[] dp = new int[n + 1];
        for (int i = 2; i <= n; i++) {
            judge = judge(i);
            if (judge == 1) dp[i] = i;
            else dp[i] = dp[judge] + dp[i / judge];
        }
        return dp[n];
    }
    public int judge(int n) {
        for (int i = 2; i < n / 2; i++) {
            if (n % i == 0) return i;
        }
        return 1;
    }
}
